package org.yao.datastructure.sparsearray;

import java.io.*;
import java.util.List;
import java.util.stream.Collectors;

/**
 * @author yaoxiang29703
 * @date 2021/3/29
 */
public class SparseArray {
    public static void main(String[] args) {
        int[][] arr = new int[11][11];
        arr[1][2] = 1;
        arr[2][4] = 2;
        arr[3][7] = 2;
        System.out.println("原始二维数组为：");
        printArray(arr);
        //转化为稀疏数组
        int[][] sparseArray = toSparseArray(arr);
        System.out.println("转化后的稀疏数组为：");
        printArray(sparseArray);
        //存入文件
        saveToFile(sparseArray, "test.txt");
        //从文件读取
        int[][] array = readFromFile("test.txt");
        System.out.println("从文件读取的稀疏数组为：");
        printArray(array);
        //转化为普通数组
        System.out.println("再次转化二维数组为：");
        int[][] normalArray = toNormalArray(array);
        printArray(normalArray);

    }

    public static void printArray(int[][] arr) {
        for (int[] ints : arr) {
            for (int anInt : ints) {
                System.out.print(anInt + "\t");
            }
            System.out.println();
        }
    }

    /**
     * 0    0	0	0	0	0
     * 0	0	1	0	0	0
     * 0	0	0	0	2	0
     * 0	0	0	0	0	0
     * 0	0	0	0	0	0
     * 转化为稀疏数组为
     * 5    6   2    行数 列数  不同的值数
     * 1    2   1    不同值的行角标 不同值的列角标 值本身
     * 2    4   2    不同值的行角标 不同值的列角标 值本身
     * 转成稀疏数组可以对原数据进行压缩
     *
     * @param arr
     * @return
     */
    public static int[][] toSparseArray(int[][] arr) {
        //遍历数据，取到不同的值的个数
        int count = 0;
        for (int[] ints : arr) {
            for (int anInt : ints) {
                if (anInt != 0) {
                    count++;
                }
            }
        }
        //创建稀疏数组，稀疏数组都是3列，行数为不同的值数加1
        int[][] sparseArray = new int[count + 1][3];
        //个第一行赋值 行数 列数  不同的值数
        sparseArray[0][0] = arr.length;
        sparseArray[0][1] = arr[0].length;
        sparseArray[0][2] = count;
        //遍历数据 得到每个不同值的坐标
        int num = 1;
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[i].length; j++) {
                if (arr[i][j] != 0) {
                    sparseArray[num][0] = i;
                    sparseArray[num][1] = j;
                    sparseArray[num][2] = arr[i][j];
                    num++;
                }
            }
        }
        return sparseArray;
    }

    public static int[][] toNormalArray(int[][] sparseArray) {
        //创建源二维数组，稀疏数组第一行记录了源数组的行数列数
        int[][] arr = new int[sparseArray[0][0]][sparseArray[0][1]];
        //遍历数组还原特殊值
        for (int i = 1; i < sparseArray.length; i++) {
            arr[sparseArray[i][0]][sparseArray[i][1]] = sparseArray[i][2];
        }
        return arr;
    }

    public static void saveToFile(int[][] sparseArray, String path) {
        FileWriter fileWriter = null;
        try {
            fileWriter = new FileWriter(path);
            for (int[] ints : sparseArray) {
                for (int anInt : ints) {
                    fileWriter.write(anInt + "\t");
                }
                fileWriter.write("\n");
            }
        } catch (IOException e) {
            e.printStackTrace();
        } finally {
            if (fileWriter != null) {
                try {
                    fileWriter.close();
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
        }
    }

    public static int[][] readFromFile(String path) {
        BufferedReader bufferedReader = null;
        int[][] sparseArray = null;
        try {
            bufferedReader = new BufferedReader(new FileReader(path));
            List<String> lines = bufferedReader.lines().collect(Collectors.toList());
            sparseArray = new int[lines.size()][3];
            String[] split;
            for (int i = 0; i < lines.size(); i++) {
                split = lines.get(i).split("\t");
                sparseArray[i][0] = Integer.parseInt(split[0]);
                sparseArray[i][1] = Integer.parseInt(split[1]);
                sparseArray[i][2] = Integer.parseInt(split[2]);
            }
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        } finally {
            if (bufferedReader != null) {
                try {
                    bufferedReader.close();
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
        }
        return sparseArray;
    }
}
